---
title: "烤鸡"
created: 2025-11-28
tags:
  - 算法
---

# 烤鸡

## 题目 [烤鸡](https://www.luogu.com.cn/problem/P2089)

![[image-0378ac72.png]]

## 思路分析

![[image-eeafb518.png]]

首先朴素做法就是 每一种调料对应每一位 每位都有1 2 3 三种选法

某种方案达到10的时候 说明10种调料都选择完毕了 结束本次递归

```typescript
#include<bits/stdc++.h>

using namespace std;

const int N=20;

int plans[N]; //1表示放一克 2表示放两克 3表示放三克

int n;

int res;

vector<vector<int>> ans;

void dfs(int u){

	if(u>10){

		int sum=0;

		for(int i=1;i<=10;i++)

			sum+=plans[i];

		if(sum==n){

			ans.push_back(vector<int>(plans + 1, plans + 11));

			res++;

		}

		return;

	}

	plans[u]=1;

	dfs(u+1);

	plans[u]=0;

	plans[u]=2;

	dfs(u+1);

	plans[u]=0;

	plans[u]=3;

	dfs(u+1);

	plans[u]=0;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	dfs(1);

	cout<<res<<endl;

	for(auto plan:ans) {

        for(int i=0;i<10;i++) {

            cout<<plan[i]<<" ";

        }

        cout<<endl;

    }

	return 0;

 }
```

这是没有考虑任何优化的 甚至1，2，3三种选择都分开写了

也能ac

![[image-b1591621.png]]

考虑一下优化 若某种方案在选到最后一位之前 就已经超过n了 就说明这种方案肯定不行 所以这个枝是可以剪去的 不妨把当前的sum也作为一个参数传入
方便剪枝

```typescript
#include<bits/stdc++.h>

using namespace std;

const int N=20;

int plans[N]; //1表示放一克 2表示放两克 3表示放三克

int n;

int res;

vector<vector<int>> ans;

void dfs(int u,int sum){

	if(sum>n)	return;

	if(u>10){

		if(sum==n){

			ans.push_back(vector<int>(plans + 1, plans + 11));

			res++;

		}

		return;

	}

	for(int i=1;i<=3;i++){

		plans[u]=i;

		dfs(u+1,sum+i);

		plans[u]=0;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	dfs(1,0);

	cout<<res<<endl;

	for(auto plan:ans) {

        for(int i=0;i<10;i++) {

            cout<<plan[i]<<" ";

        }

        cout<<endl;

    }

	return 0;

 }
```

![[image-65ed8146.png]]

## 代码实现

不剪枝

```typescript
#include<bits/stdc++.h>

using namespace std;

const int N=5010;

int path[N];

int n,res;

vector<vector<int>> ans;

void dfs(int u){

	if(u>10){

		int sum=0;

		for(int i=1;i<=10;i++){

			sum+=path[i];

		}

		if(sum==n){

			res++;

			ans.push_back(vector<int>(path+1,path+10+1));

		}

		return;

	}

	for(int i=1;i<=3;i++){

		path[u]=i;

		dfs(u+1);

		path[u]=0;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	dfs(1);

	cout<<res<<endl;

	if(res){

		for(auto plan:ans){

			for(int i=0;i<10;i++){

				cout<<plan[i]<<" ";

			}

			cout<<endl;

		}

	}

	return 0;

}
```

剪枝

```typescript
#include<bits/stdc++.h>

using namespace std;

const int N=5010;

int path[N];

int n,res;

vector<vector<int>> ans;

void dfs(int u,int sum){

	if(sum>n)

		return;

	if(u>10){

		if(sum==n){

			res++;

			ans.push_back(vector<int>(path+1,path+10+1));

		}

		return;

	}

	for(int i=1;i<=3;i++){

		path[u]=i;

		dfs(u+1,sum+i);

		path[u]=0;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	dfs(1,0);

	cout<<res<<endl;

	if(res){

		for(auto plan:ans){

			for(int i=0;i<10;i++){

				cout<<plan[i]<<" ";

			}

			cout<<endl;

		}

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[火柴棒等式|火柴棒等式]] 🏠 [[00-刷题理模型]] ➡️ [[n-皇后问题|n-皇后问题]]